package com.wjy.Data_Structure.sort.sort3;

import java.util.Arrays;

import com.wjy.Data_Structure.sort.DataWrap;

//折半插入排序
public class BinaryInsertSort {

	public static void binaryInsertSort(DataWrap[] data) {
		System.out.println("开始排序：\n");
		int arrayLength = data.length;
		for (int i = 1; i < arrayLength; i++) {
			//当整体后移时，保证data[i]的值不会丢失
			DataWrap tmp = data[i];
			int low = 0;
			int high = i - 1;
			while (low <= high) {
				int mid = (low + high) / 2;
				if (tmp.compareTo(data[mid]) > 0) {
					low = mid + 1;
				} else {
					high = mid - 1;
				}
			}
			//将low到i处的所有元素向后整体移一位
			for (int j = i; j > low; j--) {
				data[j] = data[j - 1];
			}
			data[low] = tmp;
			System.out.println(Arrays.toString(data));
		}
	}

	public static void main(String[] arys) {
		DataWrap[] data = { new DataWrap(21, ""), new DataWrap(30, ""), new DataWrap(49, ""), new DataWrap(30, ""),
				new DataWrap(16, ""), new DataWrap(9, ""), };
		System.out.println("排序之前：\n" + Arrays.toString(data));
		binaryInsertSort(data);
		System.out.println("排序之后：\n" + Arrays.toString(data));
	}
}
